
"""
106. 从中序与后序遍历序列构造二叉树
"""
from typing import Optional, List

from com.siyuan.TreeNode import TreeNode


class Solution:

    def __init__(self):
        self.dict = {}

    """
     * 分解二叉树
     * 定义build函数，构建二叉树，先构建根节点，在构建左右节点
     * 特点：后序遍历数组，最后一个节点是根节点，依次是右节点，左节点，中序遍历，根节点左边是左子树，右边是右子树
    """
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        # 将中序遍历数组存入字典中
        for i in range(len(inorder)):
            self.dict[inorder[i]] = i
        return self.build(inorder, 0, len(inorder) - 1, postorder, 0, len(postorder) - 1)

    '''遍历二叉树'''
    def build(self, inorder: List[int], in_start: int, in_end: int, postorder: List[int], post_start: int, post_end: int) -> Optional[TreeNode]:
        if in_start > in_end:
            return None
        # 根节点
        root = TreeNode(postorder[post_end])
        # 计算节点位置
        in_root_index = self.dict[postorder[post_end]]
        right_size = in_end - in_root_index

        # 前序位置
        root.left = self.build(inorder, in_start, in_root_index - 1, postorder, post_start, post_end - right_size - 1)
        # 中序位置
        root.right = self.build(inorder, in_root_index + 1, in_end, postorder, post_end - right_size, post_end - 1)
        # 后序位置
        return root